#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define MAX_SIZE 63

typedef struct ELEMENT ElementType;
typedef struct MIN_HEAP MinHeap;

struct ELEMENT {
	char ch;
	int freq;
};

struct MIN_HEAP{
	ElementType *elm;
	int capacity;
	int size;
};

struct TREE_HEAP{
	TreeNode *t[];
	int capacity;
	int size;
};

struct TREENODE {
	ElementType *elm;
	int deep;
	TreeNode *left;
	TreeNode *right;
};

void initHeap(MinHeap*);
_Bool heapEmpty(MinHeap*);
_Bool insertHeap(MinHeap*,ElementType);
_Bool deleteHeap(MinHeap*,ElementType*);
void printHeap(MinHeap*);
void buildHuffman(MinHeap*);

int main(void){
	MinHeap  heap;
	MinHeap *h=&heap;
	initHeap(h);
	int N;
	scanf("%d",&N);
	while( getc(stdin) != '\n' );
	ElementType tmp;
	char c;
	for(int i=0;i<N;i++){
		while( (c=getc(stdin)) == ' ' );
		tmp.ch=c;
		scanf("%d",&tmp.freq);
		//printf("GET:%c %d\n",tmp.ch,tmp.freq);
		insertHeap(h,tmp);
	}
	while( !heapEmpty(h) ){
		deleteHeap(h,&tmp);
		printf("CH:%c FREQ:%d\n",tmp.ch,tmp.freq);
		//printHeap(h);
	}
	return 0;
}

void initHeap(MinHeap *h){
	h->elm=malloc(sizeof(ElementType)*(MAX_SIZE+1));
	if(h->elm == NULL)
		printf("FUCK\n");
	(h->elm[0]).freq=INT_MIN;
	h->capacity=MAX_SIZE;
	h->size=0;
	return;
}

_Bool heapEmpty(MinHeap *h){
	if( 0==h->size )
		return true;
	return false;
}

_Bool insertHeap(MinHeap *h,ElementType elm){
	if( h->capacity == h->size )
		return false;
	int i=++h->size;
	for(; (h->elm[i/2]).freq > elm.freq ; i/=2){
		h->elm[i]=h->elm[i/2];
	}
	h->elm[i] = elm;
	return true;
}

_Bool deleteHeap(MinHeap *h,ElementType *elm){
	if( heapEmpty(h) )
		return false;
	*elm=h->elm[1];
	ElementType a=h->elm[h->size--];
	if( 0 == h->size )
		return true;
	int child,father;
	for( father=1 , child=2*father ; 2*father <= h->size ; father=child,child=2*father ){
		//child=2*father;
		if( child != h->size && h->elm[child+1].freq < h->elm[child].freq &&
				h->elm[child+1].freq < a.freq ){
			child++;
			h->elm[father]=h->elm[child];
		}
		else if( h->elm[child].freq < a.freq ){
			h->elm[father]=h->elm[child];
		}
		else
			break;
	}
	h->elm[father]=a;
	return true;
}

void printHeap(MinHeap *h){
	printf("SHOW HEAP\n");
	for(int i=1;i<=h->size;i++){
		printf("%c %d\n",h->elm[i].ch,h->elm[i].freq);
	}
	printf("HEAP FINISH\n");
}

TreeNode * buildHuffman(MinHeap *h){

}
